package pers.qianyu.month_202012.date_20201222;

import org.junit.*;

import java.util.*;

/**
 * 239. 滑动窗口最大值
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 *
 * @author mizzle rain
 * @date 2020-12-22 14:30
 */
public class MaxSlidingWindow {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotonicQueue q = new MonotonicQueue();
        for (int i = 0; i < k; i++) {
            q.push(nums[i]);
        }
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = k; i < nums.length; i++) {
            //System.out.println(q);
            res.add(q.max());
            q.push(nums[i]);
            q.remove(nums[i - k]);
        }
        res.add(q.max());
        int[] arr = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            arr[i] = res.get(i);
        }
        return arr;
    }

    static class MonotonicQueue {
        private LinkedList<Integer> list = new LinkedList<>();

        public void push(int x) {
            while (!list.isEmpty() && list.getLast() < x) {
                list.pollLast();
            }
            list.addLast(x);
        }

        public int max() {
            return list.getFirst();
        }

        public void remove(int x) {
            if (!list.isEmpty() && list.getFirst() == x) {
                list.pollFirst();
            }
        }

        @Override
        public String toString() {
            return "MonotonicQueue{" +
                    "list=" + list +
                    '}';
        }
    }

    @Test
    public void test1() {
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = new MaxSlidingWindow().maxSlidingWindow(arr, k);
        Assert.assertArrayEquals(result, new int[]{3, 3, 5, 5, 6, 7});
    }
}
